#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
#include <queue>
using namespace std;
  struct ListNode {
 	int val;
	struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
  };
 
class A
{
public:
    bool operator()(int x, int y)
    {
        return x > y;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<int, vector<int>, A> pq;
        for (int i = 0;i < lists.size();i++)
        {
            ListNode* cur = lists[i];
            while (cur)
            {
                pq.push(cur->val);
                cur = cur->next;
            }
        }
        ListNode* ret = nullptr;
        ListNode* cur = nullptr;
        while (!pq.empty())
        {
            if (ret == nullptr)
            {
                ret = new ListNode(pq.top());
                cur = ret;
            }
            else
            {
                cur->next = new ListNode(pq.top());
                cur = cur->next;
            }
            pq.pop();
        }
        return ret;
    }
};